package sort;

import java.util.Arrays;

//基数排序，时间复杂度 O(n*k) [k 是 桶的个数]，80000个数据下 <1s。
//快于 快排、归并
//需要一个二位数组，空间开销很大
public class RadixSort {
	public static void main(String[] args) {
		int array[] = {-1};
		radixSort(array);
		System.out.println(Arrays.toString(array));
	}

	//基数排序
	//依次按照每个数从低位到高位进行排序
	//按照该位上的值，把这个数放入对应与这个数的数组中
	public static void radixSort(int[] array) {

		//1.得到数组中得到 位数最大的数
		int max = array[0];
		for (int i = 0; i < array.length; i++) {
			if (array[i] > max) {
				max = array[i];
			}
		}
		//得到最大的数 的位数
		int maxLength = (max + "").length();


		//2.定义一个二维数组，表示10个桶，每个桶都是一个一维数组
		//需要大量空间，用空间换时间的经典算法
		int[][] bucket = new int[10][array.length];

		//为了记录每个桶中，实际存放了多少个数据，
		// 定义一个以为数组来记录，每个桶每次放入的数据个数
		int[] bucketElement = new int[10];

		//3.循环，处理

		for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
			//上面的变量 n 用于除以待处理的数，再通过取余获取每一位的数
			for (int j = 0; j < array.length; j++) {
				//依次取出每个元素的每一位上的数
				int digitOfElement = array[j] / n % 10;

				//放入到对应的桶中
				bucket[digitOfElement][bucketElement[digitOfElement]] = array[j];
				bucketElement[digitOfElement]++;
			}

			//按照桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
			int index = 0;
			//遍历每一个桶，并将桶中的数据放入到原数组
			for (int k = 0; k < bucketElement.length; k++) {
				//如果桶中有数据，才放入到原数组
				if (bucketElement[k] != 0) {
					//不为 0 说明 第K个桶中有数据
					for (int l = 0; l < bucketElement[k]; l++) {
						//取出 放入原数组
						array[index] = bucket[k][l];
						index++;
					}
				}
				//每轮处理完需要将 bucketElement[k] 变为 0
				bucketElement[k] = 0;
			}
		}


	}
}
